/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * https://leetcode.cn/problems/generate-parentheses/description/
 */
class GenerateParenthesis {
    List<String> ret = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backtrack(n,0,0,new StringBuilder());
        return ret;
    }
    public void backtrack(int n,int m,int count,StringBuilder str) {
        if(2*n==count) {
            if(m==0) {
                ret.add(str.toString());
            }
            return;
        }
        if(m<0) {//如果左括号少于右括号直接返回，因为括号不合法
            return;
        }
        //如果遇到左括号m+1
            str.append('(');
            backtrack(n,m+1,count+1,str);
            str.deleteCharAt(str.length()-1);
        //如果遇到右括号m-1    
            str.append(')');
            backtrack(n,m-1,count+1,str);
            str.deleteCharAt(str.length()-1);
            
        
    }
}